/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/distinct-subsequences
   @Language: C++
   @Datetime: 19-08-01 17:25
   */

// Method 1, DP, Time O(mn), Space O(mn)
class Solution {
public:
	int numDistinct(string &s, string &t) {
		int ls=s.length(), lt=t.length();
		vector<vector<long> > dp(ls+1,vector<long>(lt+1,0));
		dp[0][0]=1;
		for(int i=1; i<=ls; ++i){
			dp[i][0]=1;
			for(int j=1; j<=lt; ++j)
				dp[i][j]=(s[i-1]==t[j-1])?dp[i-1][j]+dp[i-1][j-1]:dp[i-1][j];
		}
		return dp[ls][lt];
	}
};

// Method 2, DP, Time O(mn), Space O(n)
class Solution {
	public:
		int numDistinct(string &s, string &t) {
			int ls=s.length(), lt=t.length();
			vector<vector<long> > dp(2,vector<long>(lt+1,0));
			dp[0][0]=dp[1][0]=1;
			for(int i=0; i<ls; ++i)
				for(int j=0; j<lt; ++j)
					dp[(i+1)&1][j+1]=dp[i&1][j+1]+(s[i]==t[j]?dp[i&1][j]:0);
			return max(dp[0][lt],dp[1][lt]);
		}
};
